(1). Field of the Invention
The invention relates to a method of converting a set of N first signal values into a set of second signal values, the relationship between these first and second signal values being given by an N-point discrete Fourier transform, N being a prime.
The invention also relates to an arrangement for carrying out the above-mentioned method and this arrangement will be denoted a Discrete-Fourier-Transform-arrangement hereinafter.
(2). Description of the Prior Art
An N-point discrete Fourier transform is a name for a special relationship between the elements of a set of N signal values {a(k)}k=0,1,2, . . . N-1 and a signal value z(n) of a set of N signal value {z(n)}n=01,2,3, . . . N-1. This relationship is defined as follows: ##EQU1##
In this expression n may assume each of the integral numbers of the field {0, 1, 2, 3, . . . , N-1}. Each quantity E and A may assume two values. In the first case the quantities may be defined by the relations: EQU E=exp(-j2.pi./N) EQU A=1 (2)
In this case expression (1) is said to express in a narrower sense a discrete Fourier transform of the set of signal values {a(k)}k=0, 1, 2, . . . , N-1.
This discrete Fourier transform in the narrow sense is usually abbreviated DFT. In this case each signal value a(k) may represent the amplitude of a sample of a time-continuous complex signal which is sampled at a frequency 1/T. Each signal value z(n) then represents the amplitude and the phase of the frequency component n/(NT) of the original complex signal.
In the second case E and A may be defined by the relations: EQU E=exp(+j2.pi./N) EQU A=1/N (3)
In this case expression (1) is sometimes said to be the inverse discrete Fourier transform of the set of values {a(k)}K=0,1,2, . . . N-1. This inverse discrete Fourier transform is usually abbreviated IDFT. In this case a signal value a(k) may represent the amplitude and the phase of the frequency component k/(NT) of a time-continuous complex signal which is sampled at a frequency 1/T and each signal value z(n) then represents the amplitude of such a sample.
As will be apparent from expression (1), a large number of arithmetic operations such as additions and multiplications must be carried out to convert the set of data elements {a(k)}k=0, 1, 2, . . . N-1 into a signal value z(n) are calculated using expression (1), a total of NZ complex multiplications and N(N-1) complex additions are required. For high values of N this means that the computation of a signal value z(n) not only takes much computational time but also requires very elaborate equipment.
Over the years a number of methods have been developed to compute such a signal value z(n). Depending on the number of arithmetic operations required, the known methods may be arranged into two categories namely the
a. the rapid methods
b. the direct methods.
The most well-known rapid method is the so-called "Fast Fourier Transform" abbreviated FFT. This method is extensively described in References 1 and 2 (see later). A novel rapid method has been proposed more recently by Winograd. This novel method is described in Reference 3. These rapid methods require a number of arithmetic operations which is proportional to N log N. These known rapid methods however have the drawback that they are only effective when N is a number which can be written as the product of a number of integers and when all, or nearly all, the N signal values z(n) must be calculated. It should further be noted that a Discrete-Fourier-Transform-arrangement the structure of which is based on one of these rapid methods can only be implemented by means of digital circuits.
The direct methods are based upon one of the following algorithms:
the Goertzel algorithm, which is described on pages 287-289 of Reference 2. A discrete-Fourier-transform arrangement whose structure is based on this Goertzel algorithm is formed by a recursive discrete filter which for pratical reasons can, however, only be implemented digitally. PA1 the Bleustein algorithm, also called the "Chirp-z-transform"-algorithm, which is described on pages 321-326 of Reference 2. A discrete-Fourier-transform arrangement whose structure is based upon this algorithm comprises a finite impulse response discrete filter (a so-called FIR-filter). Before the signal values a(k) are applied to this filter they are multiplied by a so-called chirp signal. Also the signal values produced by this filter are multiplied by such a chirp signal in order to obtain the desired signal values z(n). PA1 the Rader algorithm, also called "prime factor" algorithm, which is described in References 4 and 5. For this algorithm it is that N is a prime. PA1 a permuting step for generating a set of third signal values {b(i)}i=1,2, . . . N-1, which is formed by a permuted version of the first signal values of the first set {a(k)}k=1,2, . . . N-1. PA1 a conversion step for converting the set of third signal values {b(i)}i=1,2, . . . N-1 into the desired signal values of the set of the second signal values {z(n)-Aa(0)}n=1,2, . . . N-1; this conversion step according to the invention comprising the following steps: PA1 a first generating step for generating a set of fourth signal values {b.sub.1 (q)}q=1,2, . . . M, in which M=(N-1)/2 and b.sub.1 (q) is equal to b(q)+b(M+q); PA1 a second generating step for generating a set of fifth signal values {b.sub.2 (q)}q=1,2, . . . M, b.sub.2 (q) being equal to b(q)-b(M+q); PA1 a first auxiliary conversion step for converting the set of fourth signal values into a sixth signal value y.sub.1 (p) of a set of sixth signal values {y.sub.1 (p)}p=1,2, . . . M, in accordance with the expression: ##EQU3## in which .alpha. represents a constant and in which g is a positive integer which is equal to a primitive root of the field consisting of the numbers 1, 2, 3, . . . N-1; PA1 a second auxiliary conversion step for converting the set of fifth signal values into a seventh signal value y.sub.2 (p) of a set of seventh signal values {y.sub.2 (p)}p=1,2, . . . M, in accordance with the expression: ##EQU4## wherein .beta. represents a constant and wherein j=.sqroot.-1; and a combining step for generating the second signal value z(n)-Aa(0) in accordance with the expression: EQU z(n)-Aa(0)=y.sub.1 (p)+(-1).sup.S y.sub.2 (p) PA1 p=1,2, . . . M PA1 M=(N-1)/2
With is algorithm the set of signal values {a(k)}k=0,1,2, . . . N-1 is divided into two groups. The first group only comprises the signal value a(0), while the second group comprises the remaining signal values {a(k)}k=1,2, . . . N-1. For the generation of the signal values z(0) and N-signal values of the set {a(k)}k=0,1,2, . . . N-1 are accumulated.
For the generation of the other signal values of the set {z(n)}n=1,2, . . . N-1 the values of the set {a(k)}k=1,2, . . . N-1 are permuted. That is to say, a set of signal values {b(i)}i=1,2, . . . N-1 is generated, the signal value b(i) being equal to the signal value a(g.sup.i mod N). Herein g represents a constant which is equal to a primitive root of the field consisting of the numbers 1, 2, 3, . . . N-1 (see Reference 6). In accordance with this Radar algorithm, the set of signal values {b(i)}i=1,2, . . . N-1 thus obtained is now further converted into a set of signal values {y(m)}m=1,2, . . . N-1, wherein the relationship between the signal value y(m) and the said set of signal values b(i)i=1,2, . . . N-1 is defined by: ##EQU2## When now the signal value a(0) is added to a data element y(m) and the sum thus obtained multiplied by the factor A, the signal value z(n)=A[y(m)+a(0)] is obtained, whose number n is defined by the expression: EQU n=g.sup.m mod N (5)
In a discrete-Fourier-transform arrangement implementing this Rader algorithm, the conversion operation defined in expression (4) is implemented in a discrete filter having a filter length N-1. The discrete filter meant here and also the discrete filter included in the discrete-Fourier-transform arrangement whose structure is based upon the Bluestein-algorithm may be a "sampled data filter," or a "digital filter." For a definition of these last-mentioned terms reference is made to Reference 7.
The number of arithmetic operations required with these direct methods is proportional to N.sup.2. This number of operations decreases when the number of signal values z(n) to be determined increases. It should further be noted that the Goertzel algorithm and also the Bluestein algorithm may be used for each value of N, whereas, the Rader algorithm requires that N is a prime.